package main

import "math"

// 994. 腐烂的橘子
func main() {
	//grids := [][]int{
	//	{2, 1, 1},
	//	{1, 1, 1},
	//	{0, 1, 2},
	//}
	//grids := [][]int{
	//	{2, 1, 1},
	//	{0, 1, 1},
	//	{1, 0, 1},
	//}
	//grids := [][]int{
	//	{0},
	//}
	//grids := [][]int{
	//	{1},
	//	{2},
	//	{1},
	//	{2},
	//}
	grids := [][]int{
		{1, 2, 1, 1, 2, 1, 1},
	}
	res := orangesRotting(grids)
	println(res)
}

func orangesRotting(grid [][]int) int { // 广度优先搜索
	var res int

	if len(grid) == 0 || len(grid[0]) == 0 {
		return res
	}

	height := len(grid)
	width := len(grid[0])

	dr := []int{-1, 0, 1, 0}
	dc := []int{0, -1, 0, 1}

	var queue []int
	nodeMap := make(map[int]int)

	for i := 0; i < height; i++ {
		for j := 0; j < width; j++ {
			if grid[i][j] == 2 {
				key := width*i + j
				queue = append(queue, key)
				nodeMap[key] = key
			}
		}
	}

	if len(queue) > 0 {
		res = -1
	}

	for len(queue) > 0 {
		res++
		var copyQueue []int
		for _, item := range queue {
			copyQueue = append(copyQueue, item)
		}
		queue = queue[:0]

		for _, node := range copyQueue {
			i := node / width
			j := node % width
			for k := 0; k < 4; k++ {
				row := i + dr[k]
				col := j + dc[k]

				if row >= 0 && col >= 0 && row < height && col < width && grid[row][col] == 1 {
					key := width*row + col
					if _, exists := nodeMap[key]; !exists {
						nodeMap[key] = key
						queue = append(queue, key)
						grid[row][col] = 2
					}
				}
			}
		}
	}

	for i := 0; i < height; i++ {
		for j := 0; j < width; j++ {
			if grid[i][j] == 1 {
				return -1
			}
		}
	}

	return res
}

func maxNum(xs ...int) int {
	var res = math.MinInt
	for _, x := range xs {
		if x > res {
			res = x
		}
	}
	return res
}

//func dfs2(grid [][]int, row, column int) int { 错误
//	if len(grid) == 0 || len(grid[0]) == 0 {
//		return 0
//	}
//	height := len(grid) - 1
//	width := len(grid[0]) - 1
//	if row < 0 || column < 0 || row > height || column > width || grid[row][column] != 1 {
//		return 0
//	}
//
//	grid[row][column] = 3
//
//	dep1 := dfs2(grid, row-1, column)
//	dep2 := dfs2(grid, row+1, column)
//	dep3 := dfs2(grid, row, column-1)
//	dep4 := dfs2(grid, row, column+1)
//	return maxNum(dep1, dep2, dep3, dep4) + 1
//}

// 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
//
//值 0 代表空单元格；
//值 1 代表新鲜橘子；
//值 2 代表腐烂的橘子。
//每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
//
//返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
//
//示例 1：
//
//输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
//输出：4
//示例 2：
//
//输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
//输出：-1
//解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。
//示例 3：
//
//输入：grid = [[0,2]]
//输出：0
//解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
